package org.hmh.base;

import java.util.Arrays;

/**
 * Created this one by HMH on 2018/1/20.
 */
public class QuickSort {

    public static void sort(int[] arr) {
        qSort(arr, 0 , arr.length - 1);
    }

    private static void qSort(int[] arr, int l, int h) {
        if (l <= h) {
            int p = partition(arr, l, h);
            qSort(arr, l, p - 1);
            qSort(arr, p + 1, h);
        }
    }

    private static int partition(int[] arr, int l, int h) {
        int key = arr[l];
        int i = l + 1;
        while (i <= h) {
            if (key > arr[i]) {
                swap(arr, l++, i++);
            }else if(key < arr[i]){
                swap(arr, i, h--);
            }else{
                i++;
            }
        }
        return l;
    }

    private static void swap(int []arr, int l, int h){
        int temp = arr[l];
        arr[l] = arr[h];
        arr[h] = temp;
    }

    public static void main(String[] args){
        int arr[] = {1,5,6,7,3,2,4,5,3,123,12,3,235,6,5};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
